import java.util.*;

/**
* @description: 30. 串联所有单词的子串
* @author hewei
* @date 2022/7/25 14:31
* @version 1.0
*/

public class FindSubstring {

    public static void main(String[] args) {
        FindSubstring findSubstring = new FindSubstring();
        String[] words = {"ababa","babab"};
        System.out.println(findSubstring.findSubstring("ababababab", words));
    }

    public List<Integer> findSubstring1(String s, String[] words) {
        int n = s.length();
        int count = words[0].length();
        if (n < count * words.length) return Collections.emptyList();
        List<Integer> ans = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<String, Integer> mapCopy = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
            mapCopy.put(word, mapCopy.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < count; i++) {
            int l = i;
            int r = i;
            while (r <= s.length() - count || map.isEmpty()) {
                if (!map.isEmpty()) {
                    String temp = s.substring(r, r + count);
                    r += count;
                    if (map.containsKey(temp)) {
                        map.put(temp, map.get(temp) - 1);
                        if (map.get(temp) == 0) map.remove(temp);
                    } else {
                        if (mapCopy.containsKey(temp)) {
                            while (!s.substring(l, l + count).equals(temp)) {
                                String substring = s.substring(l, l + count);
                                map.put(substring, map.getOrDefault(substring, 0) + 1);
                                l += count;
                            }
                            l += count;
                        } else {
                            map = (HashMap<String, Integer>) mapCopy.clone();
                            l = r;
                        }
                    }
                } else {
                    ans.add(l);
                    String temp = s.substring(l, l + count);
                    map.put(temp, map.getOrDefault(temp, 0) + 1);
                    l += count;
                }
            }
            map = (HashMap<String, Integer>) mapCopy.clone();
        }
        return ans;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        int count = words[0].length();
        int n = s.length();
        int m = words.length;
        if (n < m * count) return Collections.emptyList();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            if (i + m * count > n) break;
            HashMap<String, Integer> map = new HashMap<>();
            for (int j = i; j < i + m * count; j += count) {
                String substring = s.substring(j, j + count);
                map.put(substring, map.getOrDefault(substring, 0) + 1);
            }
            for (String word : words) {
                map.put(word, map.getOrDefault(word, 0) - 1);
                if (map.get(word) == 0) map.remove(word);
            }
            int l = i;
            int r = i + m * count;
            while (n - count >= r) {
                if (map.isEmpty()) ans.add(l);
                String sL = s.substring(l, l + count);
                l += count;
                map.put(sL, map.getOrDefault(sL, 0) - 1);
                if (map.get(sL) == 0) map.remove(sL);
                String sR = s.substring(r, r + count);
                r += count;
                map.put(sR, map.getOrDefault(sR, 0) + 1);
                if (map.get(sR) == 0) map.remove(sR);
            }
            if (map.isEmpty()) ans.add(l);
        }
        return ans;
    }
}
